package slice

// BuildMaxHeap 将切片构建为大顶堆
func BuildMaxHeap[T any](nums []T, size int, f func(i, j T) bool) {
	for i := size >> 1; i >= 0; i-- {
		MaxHeapify(nums, i, size, f)
	}
}

func MaxHeapify[T any](nums []T, i int, size int, f func(i, j T) bool) {
	l, r, largest := i*2+1, i*2+2, i
	if l < size && f(nums[l], nums[largest]) {
		largest = l
	}
	if r < size && f(nums[r], nums[largest]) {
		largest = r
	}
	if largest != i {
		nums[i], nums[largest] = nums[largest], nums[i]
		MaxHeapify(nums, largest, size, f)
	}
}
